home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / utils / file / conflict.0 / conflict / conflict-6.0 / txtalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-11  |  4.4 KB  |  208 lines
  1. /******************************************************************************
  2.  * Copyright 1995 by Thomas E. Dickey.  All Rights Reserved.                  *
  3.  *                                                                            *
  4.  * You may freely copy or redistribute this software, so long as there is no  *
  5.  * profit made from its use, sale trade or reproduction. You may not change   *
  6.  * this copyright notice, and it must be included in any copy made.           *
  7.  ******************************************************************************/
  8. #ifndef    NO_IDENT
  9. static    char    Id[] = "$Id: txtalloc.c,v 6.0 1995/03/11 17:35:06 dickey Rel $";
  10. #endif
  11.  
  12. /*
  13.  * Title:    txtalloc.c (text-allocator)
  14.  * Author:    T.E.Dickey
  15.  * Created:    29 Apr 1988
  16.  *
  17.  * Function:    Maintains a balanced binary tree of character strings.
  18.  *        The algorithm is taken from "The Art of Computer Programming
  19.  *        -- Volume 3 -- Sorting and Searching", by Donald Knuth.
  20.  */
  21.  
  22. #include "conflict.h"
  23.  
  24. typedef    struct    _node    {
  25.     struct    _node    *links[2];
  26.     char        balance;    /* holds 0, -1, +1 */
  27.     char        value[1];    /* 1 for the EOS... */
  28.     } TNODE;
  29.  
  30. #define    llink    links[0]
  31. #define    rlink    links[1]
  32.  
  33.             /* definitions to make this simple, like Knuth */
  34. #define    LLINK(p)    p->llink
  35. #define    RLINK(p)    p->rlink
  36. #define    KEY(p)        p->value
  37. #define    B(p)        p->balance
  38.  
  39. #define    LINK(a,p)    p->links[(a)>0]
  40.  
  41. static    TNODE    head;
  42.  
  43. static
  44. TNODE *    new_TNODE(text)
  45.     char    *text;
  46. {
  47.     register TNODE    *p = TypeAllocN(TNODE, strlen(text));
  48.     (void)strcpy(KEY(p),text);
  49.     LLINK(p) =
  50.     RLINK(p) = 0;
  51.     B(p)     = 0;
  52.     return (p);
  53. }
  54.  
  55. char *    txtalloc(text)
  56.     char    *text;
  57. {
  58.                 /* (A1:Initialize) */
  59. register
  60. TNODE    *t    = &head,    /* 't' points to the father of 's'    */
  61.     *s    = RLINK(t),    /* 's' points to rebalancing point    */
  62.     *p    = RLINK(t),    /* 'p' moves down the tree        */
  63.     *q,
  64.     *r;
  65. register
  66. int    a;
  67. char    *value;
  68.  
  69.     if (p == 0) {
  70.         RLINK(t) = p = new_TNODE(text);
  71.         return (KEY(p));
  72.     }
  73.                 /* (A2:Compare) */
  74.     while ((a = strcmp(text, value = KEY(p))) != 0) {
  75.                 /* (A3,A4: move left/right accordingly)    */
  76.         if ((q = LINK(a,p)) != NULL) {
  77.             if (B(q)) {
  78.                 t = p;
  79.                 s = q;
  80.             }
  81.             p = q;
  82.             /* ...continue comparing */
  83.         } else {
  84.             /* (A5:Insert) */
  85.             LINK(a,p) = q = new_TNODE(text);
  86.             value = KEY(q);
  87.  
  88.             /* (A6:Adjust balance factors) */
  89.             /*
  90.              * Now the balance factors on nodes between 's' and 'q'
  91.              * need to be changed from zero to +/- 1.
  92.              */
  93.             if (strcmp(text, KEY(s)) < 0)
  94.                 r = p = LLINK(s);
  95.             else
  96.                 r = p = RLINK(s);
  97.  
  98.             while (p != q) {
  99.                 if ((a = strcmp(text, KEY(p))) != 0) {
  100.                     B(p) = (a < 0) ? -1 : 1;
  101.                     p = LINK(a,p);
  102.                 }
  103.             }
  104.  
  105.                 /* (A7:Balancing act) */
  106.             a = (strcmp(text, KEY(s)) < 0) ? -1 : 1;
  107.  
  108.             if (B(s) == 0) {
  109.                 /* ...the tree has grown higher    */
  110.                 B(s) = a;
  111.                 head.llink++;
  112.             } else if (B(s) == -a) {
  113.                 /* ...the tree has gotten more balanced    */
  114.                 B(s) = 0;
  115.             } else if (B(s) == a) {
  116.                 /* ...the tree has gotten out of balance */
  117.                 if (B(r) == a) {
  118.                     /* (A8:Single rotation) */
  119.                     p          = r;
  120.                     LINK(a,s)  = LINK(-a,r);
  121.                     LINK(-a,r) = s;
  122.  
  123.                     B(s) = B(r) = 0;
  124.                 } else if (B(r) == -a) {
  125.                     /* (A9: Double rotation) */
  126.                     p          = LINK(-a,r);
  127.                     LINK(-a,r) = LINK(a,p);
  128.                     LINK(a,p)  = r;
  129.                     LINK(a,s)  = LINK(-a,p);
  130.                     LINK(-a,p) = s;
  131.  
  132.                     if (B(p) == a)
  133.                         { B(s) = -a; B(r) = 0;    }
  134.                     else if (B(p) == 0)
  135.                         { B(s) =     B(r) = 0;  }
  136.                     else if (B(p) == -a)
  137.                         { B(s) = 0;  B(r) = a;  }
  138.  
  139.                     B(p) = 0;
  140.                 }
  141.                 /* A10:Finishing touch */
  142.                 t->links[(s == RLINK(t))] = p;
  143.             }
  144.             break;
  145.         }
  146.     }
  147.     return (value);
  148. }
  149.  
  150. /*
  151.  * Dummy entry for consistency
  152.  */
  153. void    txtfree(text)
  154.     char    *text;
  155. {
  156.     /* patch */
  157. }
  158.  
  159. /******************************************************************************/
  160. #if NO_LEAKS || defined(TEST)
  161. static
  162. void    free_TNODE(p)
  163.     TNODE    *p;
  164. {
  165.     if (p != 0) {
  166.         free_TNODE(p->llink);
  167.         free_TNODE(p->rlink);
  168.         free((char *)p);
  169.     }
  170. }
  171.  
  172. void    free_txtalloc()
  173. {
  174.     free_TNODE(head.rlink);
  175. }
  176. #endif    /* NO_LEAKS */
  177.  
  178. /******************************************************************************/
  179. #ifdef    TEST
  180. void    txtdump(p, level)
  181.     TNODE *    p;
  182.     int    level;
  183. {
  184.     register int    j;
  185.  
  186.     if (p) {
  187.         txtdump(LLINK(p),  level+1);
  188.         for (j = 0; j < level; j++)
  189.             printf(". ");
  190.         printf("%s (%d)\n", KEY(p), B(p));
  191.         txtdump(RLINK(p), level+1);
  192.     }
  193. }
  194.  
  195. int    main(argc, argv)
  196.     int    argc;
  197.     char    *argv[];
  198. {
  199.     register int    j;
  200.     for (j = 1; j < argc; j++)
  201.         (void)txtalloc(argv[j]);
  202.     txtdump(head.rlink,0);
  203.     free_txtalloc();
  204.     exit(SUCCESS);
  205.     /*NOTREACHED*/
  206. }
  207. #endif
  208.